DFS explores as "deep" as possible along each branch before backtracking. We use recursion and a `visited` set to avoid visiting the same node twice in the same traversal.
Guidance for Step 3
- Mark as visited: Add the current node (`u`) to the `visited` set.
- Print the node: Print the current node (`u`).
- Check neighbors: For each neighbor `v`, check if it is `not in` the `visited` set.
- Recurse: If a neighbor `v` hasn't been visited, make a recursive call to `solve_dfs_recursive` for that neighbor. Pass the same `adj` list and `visited` set.
def solve_dfs_recursive(u, adj, visited):
"""
Helper function for Depth-First Search.
:param u: The current node to visit
:param adj: The adjacency list of the graph
:param visited: A set of nodes already visited in this traversal
"""
# 1. Mark the current node as visited
visited.add(______)
# 2. Print it (with a space, no newline)
print(______, end=' ')
# 3. Recurse for all unvisited neighbors
# adj[u] is already sorted!
for v in adj[u]:
if v not ______ visited:
solve_dfs_recursive(______, ______, ______)
Copied!